//
// Created by xili on 2024/8/6 22:01.
// Go big or go home.
//
#include <vector>
#include <deque>
#include <climits>

using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int> &nums, int k) {
        //双端队列
        deque<int> dq;
        int n = nums.size();
        int ans = INT_MAX;
        //前缀和
        vector<long> sum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
        for (int i = 0; i <= n; i++) {
            //队列不为空，当前前缀和减去队头前缀和后仍然达标，弹出队头
            while (!dq.empty() && sum[i] - sum[dq.front()] >= k) {
                ans = min(ans, i - dq.front());
                dq.pop_front();
            }
            //队列不为空，队尾的前缀和大于当前前缀和，弹出队尾
            while (!dq.empty() && sum[i] <= sum[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};